package main

import (
	"container/list"
	"fmt"
)

type (
	entry[T comparable] struct {
		key   T
		value any
	}

	LRUCache[T comparable] struct {
		ll             *list.List
		cache          map[T]*list.Element
		capacity, size int
	}
)

func NewCache[T comparable](capacity int) *LRUCache {
	return &LRUCache[T]{
		ll:       list.New(),
		cache:    make(map[T]*list.Element),
		capacity: capacity,
	}
}

func (c *LRUCache[T]) Get(key T) any {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		ety := ele.Value.(*entry[T])
		return ety.value
	}
	return -1
}

func (c *LRUCache[T]) removeOldest() {
	if ele := c.ll.Back(); ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*entry[T])
		delete(c.cache, kv.key)
		c.size--
	}
}

func (c *LRUCache[T]) Set(key T, value any) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry[T])
		kv.value = value
	} else {
		ele := c.ll.PushFront(&entry[T]{key, value})
		c.cache[key] = ele
		c.size++
	}

	for c.capacity > 0 && c.size > c.capacity {
		c.removeOldest()
	}
}

func main() {

	capacity := 3
	//cache := &LRUCache[int]{
	//	ll:       list.New(),
	//	cache:    make(map[int]*list.Element),
	//	capacity: capacity,
	//}

	cache := NewCache[int](capacity)

	cache.Set(1, 1.1)
	cache.Set(2, 2)
	cache.Set(3, 3.33)

	fmt.Println(cache.Get(1))
	fmt.Println(cache.Get(2))
	fmt.Println(cache.Get(3))
	fmt.Println("------")

	cache.Set(3, 4)
	fmt.Println(cache.Get(3))
	fmt.Println("------")

	cache.Set(4, 4)
	fmt.Println(cache.Get(1))
	fmt.Println("------")
}
